package findknum;

import java.util.Arrays;

/**
 * 找到数组中第k小的数
 */
public class FindKNumOfQuickSort {


    /**
     * 通过递归和快速排序找到第k小的数
     * <p>
     * 思路：任意找到一个值n，然后数组中的值按照这个值进行左右分组，
     * 1，左边为小于等于数的值(逆向遍历,指针前移)
     * 2，右边为大于这个数的值(正向遍历，指针后移)
     * 当逆向遍历的指针跟正向遍历的指针重合后就表示第一次遍历成功，
     * 重合是的下标位置就是n得下标，也是n在数组中的大小的序号
     * 然后判断n所在的下标位置是否就是你要找的k
     * 1，如果k大于n的下标，则继续按照上边的遍历方式，从0到n的前一个位置区间内开始遍历（第一次）
     * 2，如果k大于n的下标，则继续按照上边的遍历方式，从n的下一个位置到end区间内遍历
     * <p>
     * <p>
     * <p>
     * 方法三：类快速排序方法快速排序的基本思想：
     * 将数组array[low...high]中某一个元素（取第一个元素）作为划分依据，
     * 然后把数组划分为三部分：
     * ①array[low...i-1]（所有的元素的值都小于或等于array[i]），
     * ②array[i]，
     * ③array[i+1...high]（所有的元素的值都大于array[i]）。
     * 在此基础上可以用下面的方法求出第k小的元素：
     * 1）如果i-low==k-1，说明array[i]就是第k小的元素，那么直接返回array[i]；
     * 2）如果i-low＞k-1，说明第k小的元素肯定在array[low...i-1]中，那么只需要递归地在array[low...i-1]中找第k小的元素即可；
     * 3）如果i-low＜k-1，说明第k小的元素肯定在array[i+1...high]中，那么只需要递归地在array[i+1...high]中找第k-（i-low）-1小的元素即可。
     * 对于数组{4,0,1,0,2,3}，第一次划分后，划分为下面三部分：{3,0,1,0,2}，{4}，{}接下来需要在{3,0,1,0,2}中找第三小的元素，
     * 把{3,0,1,0,2}划分为三部分：{2,0,1,0}，{3}，{}接下来需要在{2,0,1,0}中找第三小的元素，
     * 把{2,0,1,0}划分为三部分：{0,0,1}，{2}，{}接下来需要在{0,0,1}中找第三小的元素，
     * 把{0,0,1}划分为三部分：{0}，{0}，{1}
     * 此时i=1，low=0；（i-1=1）＜（k-1=2），
     * 接下来需要在{1}中找第k-（i-low）-1=1小的元素即可。
     * 显然，{1}中第1小的元素就是1。
     *
     * @param arr
     * @param start
     * @param end
     */
    public static void test(int[] arr, int start, int end) {
        if(start>=end){
            return;
        }
        //中间值
        int mid = arr[start];
        int i = start;
        int j = end;
        //逆向遍历找小于mid的值
        while (i < j) {
            while (i <= j && arr[j] >= mid) {
                j--;
            }
            if (i < j) {
                arr[i++] = arr[j];
            }
            //正向遍历找大于mid的值
            while (i < j && arr[i] <= mid) {
                i++;
            }
            if (i < j) {
                arr[j--] = arr[i];
            }
        }
        arr[i] = mid;
        test(arr, start, i - 1);
        test(arr, i + 1, end);
    }

    public static void sort(int [] a,int low ,int high){
        if(low>=high){
            return;
        }
        int l=low;
        int r=high;
        int midV=a[low];
        while (l<r){
            while (a[r]>= midV &&  l <r){
                r--;
            }
            if(l<r){
                a[l++]=a[r];;
            }
            while (a[l]<= midV && l <r){
                l++;
            }
            if(l<r){
                a[r--]=a[l];
            }
        }
        a[l]=midV;
        sort(a,low,l-1);
        sort(a,l+1,high);
    }

    public static void main(String[] args) {
        int[] arr = {1,3,-1,4,2,9};
        sort(arr, 0, arr.length - 1);
        Arrays.stream(arr).forEach(System.out::println);
    }
}
